#
# @lc app=leetcode.cn id=707 lang=python3
#
# [707] 设计链表
#
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# @lc code=start
class MyLinkedList:

    def __init__(self):
        self.head = ListNode()
        self.tail = ListNode()
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        temp = self.head
        idx = 0
        while temp is not None:
            if idx == index:
                return temp
            temp = temp.next
            idx += 1


    def addAtHead(self, val: int) -> None:
        newHead = ListNode(val)
        newHead.next = self.head
        self.head = newHead
        if self.size == 0:
            self.tail = self.head
        self.size += 1


    def addAtTail(self, val: int) -> None:
        newTail = ListNode(val)
        self.tail.next = newTail
        self.tail = newTail
        if self.size == 0:
            self.head = self.tail
        self.size += 1



    def addAtIndex(self, index: int, val: int) -> None:
        if index <= 0:
            self.addAtHead(val)
        elif index == self.size:
            self.addAtTail(val)
        elif index > self.size:
            return 
        else:
            preNode = self.head
            temp = self.head.next
            idx = 1
            while temp is not None:
                if idx == index:
                    newNode = ListNode(val)
                    preNode.next = newNode
                    newNode.next = temp
                    return 
                temp = temp.next 



    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return 
        if index == 0:
            self.head = self.head.next
            self.size -= 1
        else:
            idx = 1
            preNode = self.head
            temp = self.head.next
            while temp is not None:
                if idx == index:
                    preNode.next = temp.next
                    self.size -= 1
                    return
            

linkedList =  MyLinkedList()
linkedList.addAtHead(1)
linkedList.addAtTail(3)
linkedList.addAtIndex(1,2)  
linkedList.get(1)        
linkedList.deleteAtIndex(1) 
linkedList.get(1)            


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)
# @lc code=end

